// 冒泡排序，也是非常经典的排序算法，基于一种渐进逼近找最值的思想
// 它比选择排序的优越点在于
// 在遍历的过程中，提前检测到数组是有序的，从而结束排序，
// 而不像「选择排序」那样，即使输入数据是有序的，「选择排序」依然需要「傻乎乎」地走完所有的流程。
// 但基于比较仍然需要缓慢的挪移元素到指定位置，从而导致还是非常慢

export function bubbleSort(nums: number[]): number[] {
    // 冒泡大的元素
    for (let i = nums.length - 1; i >= 0; i--) {
        let isIncreasing = true;// 表示数组是否递增
        for (let j = 0; j < i; j++) {
            // 逐渐上浮元素
            if (nums[j] > nums[j + 1]) {
                [nums[j], nums[j + 1]] = [nums[j + 1], nums[j]];
                isIncreasing = false;
            }
        }
        // 可以提前检测是否已经有序而终止排序
        if (isIncreasing === true) {
            break;
        }
    }
    return nums;
}